Hãy tưởng tượng một thuật toán không phải là một chuỗi mã lệnh, mà là bản vẽ kỹ thuật chính xác để giải quyết vấn đề, độc lập với bất kỳ ngôn ngữ lập trình nào. Đó là cây cầu logic nơi dữ liệu thô (đầu vào) được chế tác cẩn thận qua một chuỗi các bước rõ ràng, hữu hạn để tạo ra kết quả mong muốn (đầu ra). Quá trình này vốn dĩ mang tính xác định — nghĩa là mọi nhánh đều có thể dự đoán được — và mang tính tổng quát, được thiết kế để giải quyết toàn bộ các loại bài toán chứ không chỉ một trường hợp ngẫu nhiên.
Cấu trúc của logic thuật toán
Trong Toán rời rạc, chúng ta định nghĩa thuật toán là một phương pháp từng bước để giải một bài toán cụ thể. Để phân biệt một danh sách việc làm đơn giản với một thuật toán toán học chính thức, chúng ta tìm kiếm hai yếu tố chính:
- Giả mã: Mô tả cấp cao, dễ đọc cho con người về logic. Nó bỏ qua cú pháp (như dấu chấm phẩy) và tập trung vào luồng hoạt động.
- Bản ghi trạng thái: Bản ghi thủ công về trạng thái của thuật toán. Chúng ta ghi lại giá trị của mọi biến tại mỗi bước để kiểm tra xem logic có đúng hay không.
Bảy đặc điểm xác định
1. Đầu vào: Thuật toán nhận dữ liệu bên ngoài để xử lý.
2. Đầu ra: Thuật toán tạo ra một kết quả hoặc lời giải.
3. Tính chính xác: Mọi lệnh đều rõ ràng và không mơ hồ.
4. Tính xác định: Kết quả trung gian là duy nhất và chỉ phụ thuộc vào đầu vào và các bước trước đó.
5. Tính hữu hạn: Quy trình chắc chắn sẽ dừng lại sau một số bước giới hạn.
6. Tính đúng đắn: Kết quả đầu ra thực sự giải được bài toán đã định.
7. Tính tổng quát: Phương pháp hoạt động với một tập hợp rộng lớn các đầu vào tiềm năng.
Cơ sở toán học: Tính chia hết
Nhiều thuật toán dựa vào lý thuyết số để hoạt động. Ví dụ như kiểm tra tính chẵn lẻ (chẵn/lẻ) hoặc xác minh số nguyên tố sử dụng định nghĩa chia hết:
Chúng ta nói một số nguyên $d$ chia hết cho $n$ (viết là $d|n$) nếu tồn tại một số nguyên $k$ sao cho $n = dk$.
Logic cốt lõi này cho phép thuật toán nhánh dựa trên mối quan hệ số học, ví dụ như xác định chữ số kiểm tra trong số thẻ tín dụng bằng thuật toán Luhn.
🎯 Nguyên tắc cốt lõi
Một thuật toán là sự hình thức hóa của logic. Nó phải hữu hạn, xác định và đúng đắn. Nếu nó chạy vòng lặp mãi hoặc tạo ra kết quả mơ hồ, thì đó chỉ là một quy trình, chứ không phải một thuật toán chính thức.